class TreeNode { 
    constructor(char) {
        this.char = char;
        this.isEnd = false;
        this.children = new Map();
    }

    findChild(char) {
        return this.children.get(char);
    }

    insertChild(char) {
        let child = this.findChild(char);
        if (!child) {
            child = new TreeNode(char);
            this.children.set(char, child);
        }
        return child;
    }

    _getPosterity() { 
        let arr = [];
        let dfs = (s, n, a) => {
            let cur = s + n.char;
            // n.children.size == 0
            if (n.isEnd) {
                a.push(cur);
            } else {
                n.children.forEach((value, key) => {
                    dfs(cur, value, a);
                });
            }
        };
        dfs("", this, arr);
        return arr;
    }
};

class Tree {
    constructor() {
        this.root = new TreeNode("");
    }

    insertBranch(str) {
        let parent = this.root;
        for (let i = 0; i < str.length; i++) {
            let char = str[i];
            parent = parent.insertChild(char);
        }
        parent.isEnd = true;
    }

    checkWord(str) {
        let temp = "";
        let i = 0;
        let l = str.length;
        while (i < l) {
            let len = this.checkWordFrom(str, i);
            if (len > 0) {
                for (let ii = 0; ii < len; ii++){
                    temp += "*";
                }
                i += len;
            } else {
                temp += str[i];
                i++;
            }
        }
        return temp;
    }

    checkWordFrom(str, i) {
        let parent = this.root;
        let idx = i;
        let l = str.length;
        while (idx < l) {
            let c = str[idx];
            if (!parent.findChild(c)) {
                return 0;
            }
            if (parent.findChild(c).isEnd) {
                return idx - i + 1;
            }
            idx++;
            parent = parent.findChild(c);
        }
        return 0;
    }

    _printTree() {
        let arr = this.root._getPosterity();
        let str = "";
        for (let i = 0; i < arr.length; i++){
            str += arr[i] + "|";
        }
        console.log(str);
    }
};

let tree = new Tree();
tree.insertBranch("H");
tree.insertBranch("ab");
tree.insertBranch("abc");
tree.insertBranch("abd");
tree.insertBranch("fuck");
tree.insertBranch("fuuk");
tree._printTree();
console.log("hhhHhhh =>", tree.checkWord("hhhHhhh"));
console.log("1ab2abc3abd3 =>", tree.checkWord("1ab2abc3abd4"));
console.log("111fuck222 =>", tree.checkWord("111fuck222"));
console.log("111fuuk222 =>", tree.checkWord("111fuuk222"));
console.log("111fudk222 =>", tree.checkWord("111fudk222"));